The Queens Problem

The Queens Problem

The queen problem is a classic problem of optimization that consists on placing a number of queens in a game board so that a queen cannot eat another queen.
El problema de las reinas es un problema clásico de optimización que consiste en colocar un número de reinas en un tablero de juegos de tal forma que una reina no pueda comerse a otra reina.

Problem 1
Using Microsoft Visual Studio create a Simulated Annealing Application using Wintempla. Set the name of the program to Queens.
Usando Microsoft Visual Studio cree una Simulated Annealing Application usando Wintempla. Fije el nombre del programa a Queens.

Problem 2
Add the Paint event to the Queens project:
  1. Open the Queens.cpp file
  2. From the toolbar execute Wintempla
  3. Double click anywhere in the area of the window to open the properties dialog of the main window
  4. Open the Event tab
  5. Select the events as shown: App, Destroy, Open, Paint and Timer
  6. Press OK to close the properties dialog
  7. Press OK to close Wintempla
Agregue el evento de Paint al proyecto Queens:
  1. Abra el archivo Queens.cpp
  2. Desde la barra de herramienta ejecute Wintempla
  3. Haga doble click en cualquier lugar de la ventana para abrir el diálogo de propiedades de la ventana principal
  4. Abra la pestaña de eventos
  5. Seleccione los eventos cómo se muestra: : App, Destroy, Open, Paint y Timer
  6. Presione OK para cerrar el diálogo de propiedades
  7. Presione OK para cerrar Wintempla

Event1

Event2

Event3

Queen Board Perturbation

There are many ways to perturb the position of the queens in the board. For instance, a random position is generated; if there is a queen in that position, the queen is moved to an empty random position.
Hay muchas formas para perturbar la posición de las reinas en el tablero. Por ejemplo, una posición aleatoria se genera; si hay una reina en esa posición, la reina se mueve a una casilla vacía aleatoria.

Problem 3
Implement the Solution Coding for the queens problem.
Implemente la Codificación de la Solución para el problema de las reinas.

Solution 3
The coding of this problem requires a matrix called board to store integer values as shown. Edit the Solution.h and Solution.cpp files as shown.
La codificación de este problema requiere de una matriz llamada board para almacenar valores enteros como se muestra. Edite los archivos Solution.h y Solution.cpp.

Solution.h
#pragma once
#define BOARD_SIZE 20
#define QUEEN -1
#define EMPTY 0
#define ERROR_QUEEN 1

class Solution : public Math::ISimAnneal
{
public:
     Solution(void);
     ~Solution(void);
     static bool IsError(int board[][BOARD_SIZE], int row, int col);
     //___________________________________________ Solution variables
     int board[BOARD_SIZE][BOARD_SIZE];
     //___________________________________________ Math::ISimAnneal
     void SimAnnealInitialize();
     void SimAnnealPerturb(Math::ISimAnneal& original, double temperature, double initialTemperature);
     void SimAnnealCopy(const Math::ISimAnneal& source);
     double SimAnnealGetError();
};

Solution.cpp
#include "StdAfx.h"
#include ".\Solution.h"

Solution::Solution(void)
{
     int row, col;
     //______________________________________ Place all Queens in the first row
     for(row = 0; row < BOARD_SIZE; row++)
     {
          for(col = 0; col < BOARD_SIZE; col++)
          {
               if (row == 0)
               {
                    board[row][col] = ERROR_QUEEN;
               }
               else
               {
                    board[row][col] = EMPTY;
               }
          }
     }
}

Solution::~Solution(void)
{
}

// Returns true if there is an error in the Queen located in the specified row and column
bool Solution::IsError(int board[][BOARD_SIZE], int row, int col)
{
     ...
     return ...;
}

void Solution::SimAnnealInitialize()
{
     ...
}

void Solution::SimAnnealPerturb(Math::ISimAnneal& original, double temperature, double initialTemperature)
{
     Solution& source = (Solution&)original;
     ...
}

void Solution::SimAnnealCopy(const Math::ISimAnneal& source)
{
     Solution& ssource = (Solution&)source;
     int row, col;
     //_____________________________________ Copy the original board
     for(row = 0; row <BOARD_SIZE; row++)
     {
          for(col = 0; col <BOARD_SIZE; col++)
          {
               board[row][col] = ssource.board[row][col];
          }
     }
}

double Solution::SimAnnealGetError()
{     
     ...
     return ...;
}



Problem 4
Edit the Queens.h and Queens.cpp files as shown to set the position of the queens. The Window_Paint function provides the code to draw the queens in the game board. When the simulation ends, the solution is displayed.
Edite los archivo Queens.h y Queens.cpp como se muestra para fijar la posición de las reinas. La función Window_Paint proporciona el código para dibujar reinas en el tablero. Cuando la simulación termina, la solución es mostrada.

QueenLocation

Queens.h
#pragma once //______________________________________ Queens.h
#include "resource.h"
#include "Solution.h"
#define MAIN_TIMER 1
#define WORK_ID 1
class Queens: public Win::Window
{
public:
     Queens()
     {
     }
     ~Queens()
     {
     }
     //__________________________ Used for display purposes
     int board[BOARD_SIZE][BOARD_SIZE];
     //
     Mt::DoubleTs error;
     ...


Queens.cpp
#include "stdafx.h" //________________________________________ Queens.cpp
#include "Queens.h"

int APIENTRY wWinMain(HINSTANCE hInstance, HINSTANCE , LPTSTR cmdLine, int cmdShow){
     Queens app;
     app.CreateMainWindow(L"Queens", cmdShow, IDI_QUEENS, NULL, (HBRUSH)(COLOR_WINDOW+1), hInstance);
     return app.MessageLoop(IDC_QUEENS);
}

void Queens::Window_Open(Win::Event& e)
{
     //_____________________________________ Initialize the Random Generator
     Math::Statistics::random_generator.seed((unsigned int)::GetTickCount());
     //
     int row, col;
     //_______________Copy the board from the solution so that we can display it
     for(row = 0; row < BOARD_SIZE; row++)
     {
          for(col = 0; col < BOARD_SIZE; col++)
          {
               board[row][col] = solution.board[row][col];
          }
     }
     //
     simAnneal.goal =...
     simAnneal.initialTemp = ...
     simAnneal.finalTemp = ...
     simAnneal.numTemps = ...
     simAnneal.numIterations =...
     simAnneal.cycles = ...
     simAnneal.isCoolingScheduleLinear = ...
     simAnneal.Setup(error, solution, solutionWork1, solutionWork2);
     simAnneal.SetPostMessage(hWnd, WM_APP, 0, WORK_ID);
     threadObject.StartThread(simAnneal);
     this->timer.Set(MAIN_TIMER, 1000); //Every second
}

void Queens::Window_Destroy(Win::Event& e)
{
     this->timer.Kill(MAIN_TIMER);
     ::PostQuitMessage(0);
     e.returnValue = 0;
}

void Queens::Window_Timer(Win::Event& e)
{
     if (e.wParam== MAIN_TIMER)
     {
          wchar_t info[128];
          const double derror = error.Get();
          _snwprintf_s(info, 128, _TRUNCATE, L"error=%g, progress=%g", derror, threadObject.Progress);
          this->SetWindowText(info);
     }
}

void Queens::Window_App(Win::Event& e)
{
     if (e.lParam == WORK_ID)
     {
          this->timer.Kill(MAIN_TIMER);
          threadObject.WaitForExit();
          this->Text = L"Done!";
          int row, col;
          //_______________Copy the solution so that we can display it
          for (row = 0; row < BOARD_SIZE; row++)
          {
               for (col = 0; col < BOARD_SIZE; col++)
               {
                    board[row][col] = solution.board[row][col];
               }
          }
          //_________________ Update the errors
          for (row = 0; row < BOARD_SIZE; row++)
          {
               for (col = 0; col < BOARD_SIZE; col++)
               {
                    if (board[row][col] == EMPTY) continue;
                    //___________________ Find Error Queens
                    if (Solution::IsError(board, row, col) == true)
                    {
                         board[row][col] = ERROR_QUEEN;
                    }
                    else
                    {
                         board[row][col] = QUEEN;
                    }
               }
          }
          this->Repaint(NULL, true);
     }
}

void Queens::Window_Paint(Win::Event& e)
{
     CG::Gdi gdi(hWnd, true, false);
     const double delta = MINIMUM(width, height)/BOARD_SIZE;
     CG::Font font(L"Arial", (int)(0.8*delta));
     int row, col, x, y;

     RECT rc;
     gdi.Select(font);
     gdi.SetBkMode(true);
     wchar_t queen[2];
     queen[0] = 0x2655;
     queen[1] = '\0';

     //______________________________________ Draw the Queens
     for(row = 0; row < BOARD_SIZE; row++)
     {
          for(col = 0; col < BOARD_SIZE; col++)
          {
               if (board[row][col] == EMPTY) continue; // Nothing to draw
               //_______________________ Select the color to draw the Queen
               if (board[row][col] == ERROR_QUEEN)
               {
                    gdi.SetTextColor(RGB(255, 0, 0));
               }
               else //__ QUEEN
               {
                    gdi.SetTextColor(RGB(0, 0, 0));
               }
               //_________Calculate the surronding box of the Queen, so that it can be centered in it
               x = (int)(col*delta+0.5);
               y = (int)(row*delta+0.5);
               rc.left = x;
               rc.right = (int)(x+delta+0.5);
               rc.top = y;
               rc.bottom = (int)(y + delta+0.5);
               //______________________ Draw the Queen
               gdi.TextOut(rc, queen);
          }
     }

     //_____________________________________ Draw the Game Board
     for(row=0; row<BOARD_SIZE; row++)
     {
          x = (int)((row+1)*delta+0.5);
          y = (int)((row+1)*delta+0.5);
          gdi.Line(x, 0, x, (int)(delta*BOARD_SIZE+0.5));
          gdi.Line(0, y, (int)(delta*BOARD_SIZE+0.5), y);
     }
}

Problem 5
Implement the Initialization for the queens problem by writing the code of the SimAnnealInitialize() function in the Solution.cpp file.
Implemente la Inicialización para el problema de las reinas escribiendo el código de la función SimAnnealInitialize() en el archivo Solución.cpp.

Problem 6
Implement the Error Evaluation for the queens problem by writing the code of the SimAnnealGetError () function in the Solution.cpp file. Remember that a queen can eat another queen that is in the same row, column or diagonal. Thus, each queen that can be eaten counts as an error.
Implemente la Evaluación del Error para el problema de las reinas escribiendo el código de la función SimAnnealGetError() en el archivo Solución.cpp. Recuerde que una reina se puede comer a otra reina que se encuentra en el mismo renglón, columna o diagonal. Así, cada reina que puede ser comida se cuenta como un error.

Problem 7
Implement the Perturbation for the queens problem by writing the code of the SimAnnealPerturb() function in the Solution.cpp file.
Implemente la Perturbación para el problema de las reinas escribiendo el código de la función SimAnnealPerturb() en el archivo Solución.cpp.

Problem 8
Set the simulated annealing parameters (number of temperature, initial temperature, ...) and run the simulation, you must get a solution similar to the solution shown below.
Fije los parámetros del templado simulado (los números de temperaturas, la temperatura inicial, ...) y corre la simulación, usted debe obtener una solución similar a la solución mostrada debajo.

Solution

© Copyright 2000-2021 Wintempla selo. All Rights Reserved. Jul 22 2021. Home